package geekstudy.week8;

/**
 *
 * 14. 最长公共前缀
 * https://leetcode-cn.com/problems/longest-common-prefix/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：1 ms, 在所有 Java 提交中击败了79.36% 的用户
 * 内存消耗：36.3 MB, 在所有 Java 提交中击败了84.23% 的用户
 *
 *
 */
public class Week8LongestCommonPrefix {

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int minLength = Integer.MAX_VALUE;
        for (String str : strs) {
            minLength = Math.min(minLength, str.length());
        }
        int lowPosition = 0;
        int highPosition = minLength;
        for (;lowPosition < highPosition;) {
            int middle = (highPosition - lowPosition + 1) / 2 + lowPosition;
            if (isCommonPrefix(strs, middle)) {
                lowPosition = middle;
            } else {
                highPosition = middle - 1;
            }
        }
        return strs[0].substring(0, lowPosition);

    }


    public boolean isCommonPrefix(String[] strs, int length) {
        String zeroString = strs[0].substring(0, length);
        for (int size = 1; size < strs.length; size++) {
            String temp = strs[size];
            for (int subSize = 0; subSize < length; subSize++) {
                if (zeroString.charAt(subSize) != temp.charAt(subSize)) {
                    return false;
                }
            }
        }
        return true;
    }


}
